package qujian;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 56. 合并区间
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * <p>
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * <p>
 * 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-03 11:06
 */
public class L56 {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        List<int[]> list = new ArrayList<>();
        //数组第一个数排序
        Arrays.sort(intervals, Comparator.comparingInt(x -> x[0]));
        //左右指针，如果只用一个，不好赋值
        int left = 0;
        int right = 0;
        while (right < intervals.length) {
            int leftBound = intervals[left][0];
            int rightBound = intervals[right][1];
            while (right < intervals.length && rightBound >= intervals[right][0]) {
                rightBound = Math.max(rightBound, intervals[right][1]);
                right++;
            }
            list.add(new int[]{leftBound, rightBound});
            left = right;
        }

        return list.toArray(new int[list.size()][]);
    }
}
